package org.example.myleet.p919;

import org.example.myleet.Utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class CBTInserter {

    private TreeNode root;

    private Queue<TreeNode> queue;

    private TreeNode curNode;

    private boolean left;

    public CBTInserter(TreeNode root) {
        this.root = root;
        //利用BFS先找到待插入的位置
        queue = new LinkedList<>();
        queue.add(root);
        outer:
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode cur = queue.peek();
                if (null == cur.left || null == cur.right) {
                    //如果遇到队列头部节点的子节点有空的情况，说明这个节点就是要找的待插入节点，停止BFS（break）
                    if (null == cur.left) {
                        //如果左子节点为空，则左子节点标记为待插入
                        left = true;
                    } else {
                        //否则就是右子节点为空，标记右子节点待插入，并且将左子节点加入队列尾部，并弹出队列头，和下面的插入是呼应的
                        //原因是cur节点在插入右子节点后将被跳过，因此不需要继续待在队列中
                        curNode = cur;
                        queue.add(cur.left);
                        queue.poll();
                        left = false;
                    }
                    break outer;
                }
                //cur节点满二叉，弹出，继续BFS
                cur = queue.poll();
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }
    }

    public int insert(int val) {
        if (left) {
            //curNode左子节点待插入，插入到curNode左子节点
            curNode = queue.poll();
            curNode.left = new TreeNode(val);
            queue.add(curNode.left);
            //标记curNode右子节点待插入
            left = false;
        } else {
            //curNode右子节点待插入，插入到curNode右子节点
            curNode.right = new TreeNode(val);
            queue.add(curNode.right);
            //标记队列中下一个节点的左子节点待插入
            left = true;
        }
        return curNode.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
